1. Field
The present invention relates generally to evaluating a cipher structure in terms of resistance to differential cryptanalysis and linear cryptanalysis.
2. Background
The field of communications has many applications including, e.g., paging, wireless local loops, Internet telephony, and satellite communication systems. An exemplary application is a cellular telephone system for mobile subscribers. (As used herein, the term “cellular” system encompasses both cellular and personal communications services (PCS) system frequencies.) Modern communication systems, such as a wireless communication system, designed to allow multiple users to access a common communications medium have been developed for such cellular systems. These modern communication systems may be based on multiple access techniques such as code division multiple access (CDMA), time division multiple access (TDMA), frequency division multiple access (FDMA), space division multiple access (SDMA), polarization division multiple access (PDMA), or other modulation techniques known in the art. These modulation techniques demodulate signals received from multiple users of a communication system, thereby enabling an increase in the capacity of the communication system. In connection therewith, various wireless communication systems have been established including, e.g., Advanced Mobile Phone Service (AMPS), Global System for Mobile communication (GSM), and other wireless systems.
In FDMA systems, the total frequency spectrum is divided into a number of smaller sub-bands and each user is given its own sub-band to access the communication medium. Alternatively, in TDMA systems, the total frequency spectrum is divided into a number of smaller sub-bands, each sub-band is shared among a number of users, and each user is allowed to transmit in predetermined time slots using that sub-band. A CDMA system provides potential advantages over other types of systems, including increased system capacity. In CDMA systems, each user is given the entire frequency spectrum for all of the time, but distinguishes its transmission through the use of a unique code.
A CDMA system may be designed to support one or more CDMA standards such as (1) the “TIA/EIA-95-B Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System” (the IS-95 standard), (2) the standard offered by a consortium named “3rd Generation Partnership Project” (3GPP) and embodied in a set of documents including Document Nos. 3G TS 25.211, 3G TS 25.212, 3G TS 25.213, and 3G TS 25.214 (the W-CDMA standard), and (3) the standard offered by a consortium named “3rd Generation Partnership Project 2” (3GPP2) and embodied in “TR-45.5 Physical Layer Standard for cdma2000 Spread Spectrum Systems” (the IS-2000 standard).
In the above named CDMA communication systems and standards, the available spectrum is shared simultaneously among a number of users, and suitable techniques are available to provide services, such as voice and data services.
A typical mobile station uses cryptography for secure communications. One type of cryptography uses a cipher structure, such as a substitution-permutation network, which is based on the properties of diffusion and confusion. Diffusion relates to the dependency of output bits to input bits. Transposition (rearranging the order of symbols) and linear transformations are mechanisms of diffusion. Confusion refers to making the relationship between a key and the ciphertext as complex and involved as possible. Substitution, where a symbol is replaced by another, is a confusion mechanism. A substitution box (S-box) is a confusion element. Such cipher structures generally use identically-sized S-boxes to simply design even though the use of differently-sized S-boxes may have cryptographic advantages. One difficulty is the lack of a technique to evaluate a cipher using differently-sized S-boxes in terms of resistance to cryptanalysis, thereby tending to impede the acceptance and use of such cipher structures.
There is therefore a need for evaluating and optimizing a cipher structure in terms of resistance to cryptanalysis, in a cost effective and efficient manner.